package bintree.map_set.leetcode;

import java.util.HashMap;
import java.util.Map;

public class Num138复制带随机指针的链表 {
    public Node copyRandomList(Node head) {
        // 1.遍历原链表，构造Map集合维护原链表节点和新链表结点的映射关系
        // 原1 = 新1
        Map<Node,Node> map =new HashMap<>();
        for (Node x  = head ; x!=null; x=x.next) {
            Node node = new Node(x.val);
            map.put(x,node);
        }
        // 1.遍历原链表，构造Map集合维护原链表节点和新链表结点的映射关系
        // 原1 = 新1
        for (Node x = head; x!=null; x = x.next){
            // 原1.next = 原3
            // 新1.next = 新3
            map.get(x).next=map.get(x.next);
            // 原1.random = 原5
            // 新1.random = 新5
            map.get(x).random = map.get(x.random);
        }
        // 新1 => 原1
        return map.get(head);
    }
}
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}